package xyz.scootaloo.oj.leetcode;

import org.junit.Test;

/**
 * 中心扩散
 * 超出时间限制
 * @author flutterdash@qq.com
 * @since 2021/3/22 21:46
 */
public class P84b {

    @Test
    public void testFunc() {
        int[] input = {2, 1, 5, 6, 2, 3};
        System.out.println(largestRectangleArea(input));
    }

    public int largestRectangleArea(int[] heights) {
        int len = heights.length;
        int maxArea = 0, left, right;
        for (int pos = 0; pos<len; pos++) {
            int currentHeight = heights[pos];
            left = right = pos;
            while (left > 0 && heights[left - 1] >= currentHeight) {
                left--;
            }
            while (right < (len - 1) && heights[right + 1] >= currentHeight) {
                right++;
            }

            int width = (right - left) + 1;
            maxArea = Math.max(maxArea, width * currentHeight);
        }
        return maxArea;
    }

}
